부산대학교자료구조
Scientific Inference Lab

Last In, First Out

Stack ADT

스택(stack)은 맨 위(top)라고 부르는 한쪽 끝에서만 값을 넣고 빼는 ADT다. 가장 나중에 넣은 값을 가장 먼저 꺼내는 LIFO 순서는 값의 종류가 아니라 push와 pop의 호출 순서로 정해진다.

push(x)x를 맨 위에 추가하고 반환값이 없다.
pop()과 peek()둘 다 맨 위 값을 반환하지만 pop만 그 값을 삭제한다.
구현의 끝 선택Python list는 오른쪽 끝, SLList는 머리(head)를 맨 위로 둔다.

push와 pop이 같은 끝에서 일어나 넣은 순서가 뒤집힌다

단계를 옮기면 연산 하나가 실행되고, 스택의 맨 위, 반환값, 원소 수가 바뀐다. 4, dog, True, 8.4를 차례로 넣은 뒤 꺼낸다.

바닥

    왼쪽 기둥은 스택이며 위쪽이 맨 위다. 초록 칸이 맨 위 값이다. 오른쪽 목록은 연산 순서이고 짙은 줄이 방금 실행한 연산이다.

    어느 끝을 맨 위로 두는지에 따라 같은 LIFO도 비용이 다르다

    구현 방식과 원소 수 n을 바꾸면 push 한 번에 옮기는 원소 수와 비용이 바뀐다. 세 구현 모두 LIFO 결과는 같다.

    칸 하나가 저장된 원소다. 초록 칸은 새로 push한 값, 파란 칸은 그 push 때문에 한 칸씩 옮겨진 원소다.